package leetcode

/*
 * @lc app=leetcode.cn id=188 lang=golang
 *
 * [188] 买卖股票的最佳时机 IV
 */

// @lc code=start
func maxProfit(k int, prices []int) int {
	n := len(prices)
	if n < 2 || k == 0 {
		return 0
	}

	if n/2 < k {
		k = n / 2
	}
	buys := make([]int, k)
	sells := make([]int, k)
	for i := 0; i < k; i++ {
		buys[i] = -prices[0]
	}
	for i := 1; i < n; i++ {
		for j := 0; j < k; j++ {
			if j == 0 {
				buys[j] = max(buys[j], -prices[i])
			} else {
				buys[j] = max(buys[j], sells[j-1]-prices[i])
			}
			sells[j] = max(sells[j], buys[j]+prices[i])
		}
	}
	return sells[k-1]
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

// @lc code=end
